package puzzle.projecteuler.p200;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

import astudy.util.Combination;


public class Problem103C {

	/**
	 * answer: 
	 * 		sum=255	: 20 31 38 39 40 42 45
	 * 这个问题只用了简单的遍历，没有采用减枝等方法。很多地方有待优化。 
	 * @param args
	 */
	public static void main(String[] args) {
		
		List<Integer[]> arrays = findAll(7, 50);
		if (arrays != null) {
			for (Integer[] a: arrays) {
				System.out.print(sum(a) + "\t: ");
				print(a);
			}
		} else {
			System.out.print("Not Found!");
		}
	}
	

	/**
	 * 返回所有长度为n，但最大元素不大于max的满足条件的集合。
	 * 注意，满足条件的集合，其子集也满足条件。
	 * @param n
	 * @param max
	 */
	private static List<Integer[]> findAll(Integer n, Integer max) {
		
		LinkedList<Integer[]> arrays = new LinkedList<Integer[]>();
		for (Integer i = 1; i <= max; i ++) {
			arrays.add(new Integer[] {i});
		}
		while (true) {
			if (arrays.isEmpty()) {
				return null;
			}
			Integer[] cur = arrays.peek();
			if (cur.length == n) {
				return arrays;
			} else {
				arrays.poll();
				for (Integer i = cur[cur.length-1]+1; i <= max; i ++) {
					Integer[] tmp = new Integer[cur.length+1];
					System.arraycopy(cur, 0, tmp, 0, cur.length);
					tmp[tmp.length-1] = i;
					if (check(tmp)) {
						arrays.add(tmp);
					}
				}
			}
		}
	}
	
	/**
	 * 测试指定的集合是否满足条件 
	 * @param array
	 * @return
	 */
	private static boolean check(Integer[] array) {

		int[] indexes = new int[array.length];
		for (Integer i = 0; i < indexes.length; i ++) {
			indexes[i] = 0;
		}
		int[] minArray = new int[array.length];	//记录每种长度的集合,和的最小值
		minArray[0] = 0;
		int[] maxArray = new int[array.length];	//记录每种长度的集合,和的最大值
		maxArray[0] = 0;
		for (int i = 0; i < array.length; i ++) {
			minArray[i] = -1;
			maxArray[i] = -1;
		}
		Set<Integer> sums = new HashSet<Integer>();	//记录所有的集合和
		while ((indexes = Combination.next(array.length+1, indexes)) != null) {
			Integer[] tmp = new Integer[indexes.length];
			int count = 0;
			for (Integer i = 0; i < tmp.length; i++) {
				if (indexes[i] == 0) {
					tmp[i] = null;
				} else {
					count ++;
					tmp[i] = array[indexes[i]-1];
				}
			}
			Integer sum = sum(tmp);
			if (sums.contains(sum)) {
				return false;
			} else {
				sums.add(sum);
				if (maxArray[count-1] == -1 || sum > maxArray[count-1]) {
					maxArray[count-1] = sum;
				}
				if (minArray[count-1] == -1 || sum < minArray[count-1]) {
					minArray[count-1] = sum;
				}
			}
		}
		for (int i = 1; i < array.length-1; i ++) {
			if (maxArray[i] >= minArray[i+1]) {
				return false;
			}
		}
		return true;
	}
	
	private static void print(Integer[] a) {

		for (Integer i = 0; i < a.length; i ++) {
			System.out.print(a[i]+ " ");
		}
		System.out.println();
	}
	
	private static Integer sum(Integer[] a) {
		
		Integer s = 0;
		for (Integer i = 0; i < a.length; i ++) {
			if (a[i] != null) {
				s += a[i];
			}
		}
		return s;
	}
}
